SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Self-synchronizing code</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Self-synchronizing code</span></span>

</h1>

</header>

</p>

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="Self-clocking_signal" title="Self-clocking signal">Self-clocking signal</a> or <a href="Self-similar_process" title="Self-similar process">Self-similar process</a>.</div>

<p>In <a href="Coding_theory" title="Coding theory">coding theory</a>, especially in <a href="Telecommunications" title="Telecommunications">telecommunications</a>, a <b>self-synchronizing code</b> is a <a href="Uniquely_decodable_code" class="mw-redirect" title="Uniquely decodable code">uniquely decodable code</a> in which the <a href="Symbol_(data)" class="mw-redirect" title="Symbol (data)">symbol</a> stream formed by a portion of one <a href="Code_word_(communication)" title="Code word (communication)">code word</a>, or by the overlapped portion of any two adjacent code words, is not a valid code word.<sup id="cite_ref-Glossary_1-0" class="reference"><a href="#cite_note-Glossary-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Put another way, a set of strings (called "code words") over an alphabet is called a self-synchronizing code if for each string obtained by concatenating two code words, the substring starting at the second symbol and ending at the second-last symbol does not contain any code word as substring. Every self-synchronizing code is a <a href="Prefix_code" title="Prefix code">prefix code</a>, but not all prefix codes are self-synchronizing.

</p><p>Other terms for self-synchronizing code are <b>synchronized code</b><sup id="cite_ref-Brestel-Perrin-Reutenauer_2010_2-0" class="reference"><a href="#cite_note-Brestel-Perrin-Reutenauer_2010-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> or, ambiguously, <b>comma-free code</b>.<sup id="cite_ref-Brestel-Perrin_1985_3-0" class="reference"><a href="#cite_note-Brestel-Perrin_1985-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> A self-synchronizing code permits the proper <a href="Frame_synchronization" title="Frame synchronization">framing</a> of transmitted code words provided that no uncorrected errors occur in the <a href="Data_stream" title="Data stream">symbol stream</a>; external <a href="Synchronization" title="Synchronization">synchronization</a> is not required. Self-synchronizing codes also allow recovery from uncorrected errors in the stream; with most prefix codes, an uncorrected error in a single <a href="Bit" title="Bit">bit</a> may propagate errors further in the stream and make the subsequent data <a href="Data_corruption" title="Data corruption">corrupted</a>.

</p><p>Importance of self-synchronizing codes is not limited to <a href="Data_transmission" class="mw-redirect" title="Data transmission">data transmission</a>. Self-synchronization also facilitates some cases of <a href="Data_recovery" title="Data recovery">data recovery</a>, for example of a <a href="Character_encoding" title="Character encoding">digitally encoded text</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<ul><li><a href="UTF-8" title="UTF-8">UTF-8</a> is self-synchronizing because the leading byte (<code>11xxxxxx</code>) and subsequent bytes (<code>10xxxxxx</code>) of a multi-byte code point have different bit patterns.</li>

<li><a href="High_Level_Data_Link_Control" class="mw-redirect" title="High Level Data Link Control">High Level Data Link Control</a> (HDLC)</li>

<li><a href="Advanced_Data_Communication_Control_Procedures" title="Advanced Data Communication Control Procedures">Advanced Data Communication Control Procedures</a> (ADCCP)</li>

<li><a href="Fibonacci_coding" title="Fibonacci coding">Fibonacci coding</a></li></ul>

<p>Counterexamples:

</p>

<ul><li>The prefix code {00, 11} is not self-synchronizing; while 0, 1, 01 and 10 are not codes, 00 and 11 are.</li>

<li>The prefix code {<i>ab</i>,<i>ba</i>} is not self-synchronizing because <i>abab</i> contains <i>ba</i>.</li>

<li>The prefix code <i>b</i><sup>∗</sup>a (using the <a href="Kleene_star" title="Kleene star">Kleene star</a>) is not self-synchronizing (even though any new code word simply starts after <i>a</i>) because code word <i>ba</i> contains code word <i>a</i>.</li></ul>

<li><a href="Comma_code" title="Comma code">Comma code</a></li>

<li><a href="Consistent_overhead_byte_stuffing" class="mw-redirect" title="Consistent overhead byte stuffing">Consistent overhead byte stuffing</a></li>

<li><a href="Dynkin_sequence" class="mw-redirect" title="Dynkin sequence">Dynkin sequence</a></li>

<li><a href="Kraus_principle" class="mw-redirect" title="Kraus principle">Kraus principle</a></li>

<li><a href="Kruskal's_principle" class="mw-redirect" title="Kruskal's principle">Kruskal's principle</a></li>

<li><a href="Overlapping_instructions" class="mw-redirect" title="Overlapping instructions">Overlapping instructions</a></li>

<li><a href="Pollard's_lambda_method" class="mw-redirect" title="Pollard's lambda method">Pollard's lambda method</a></li>

<li><a href="Self-clocking_signal" title="Self-clocking signal">Self-clocking signal</a></li>

<li><a href="Self-synchronizing_block_code" class="mw-redirect" title="Self-synchronizing block code">Self-synchronizing block code</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://glossary.atis.org/glossary/self-synchronizing-code/?char=S&page_number=22&sort=ASC">"Self-synchronizing code – Glossary"</a>.</cite></span>

</li>

<li id="cite_note-Brestel-Perrin-Reutenauer_2010-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-Brestel-Perrin-Reutenauer_2010_2-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFBerstelPerrinReutenauer2010" class="citation book cs1">Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). <i>Codes and automata</i>. Encyclopedia of Mathematics and its Applications. Vol. 129. Cambridge, UK: <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. p. 137. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-88831-8</bdi>. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:1187.94001">1187.94001</a>.</cite></span>

</li>

<li id="cite_note-Brestel-Perrin_1985-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-Brestel-Perrin_1985_3-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFBerstelPerrin1985" class="citation book cs1">Berstel, Jean; Perrin, Dominique (1985). <i>Theory of Codes</i>. Pure and Applied Mathematics. Vol. 117. <a href="Academic_Press" title="Academic Press">Academic Press</a>. p. 377. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:0587.68066">0587.68066</a>.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite class="citation book cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20220122224547/https://www.its.bldrdoc.gov/fs-1037/fs-1037c.htm">"self-synchronizing code"</a>. <a href="Federal_Standard_1037C" title="Federal Standard 1037C"><i>Federal Standard 1037C: Telecommunications: Glossary of Telecommunication Terms</i></a>. <a href="General_Services_Administration" title="General Services Administration">General Services Administration</a>. 1996-08-06. Archived from <a rel="nofollow" class="external text" href="https://www.its.bldrdoc.gov/fs-1037/fs-1037c.htm">the original</a> on 2022-01-22.</cite></li>

This article is issued from <a class="external text" title="Last edited on 2024-09-16" href="https://en.wikipedia.org/wiki/?title=Self-synchronizing_code&oldid=1245937399">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>